package faceQuestion;

import java.util.*;

/**
 * Description： TODO
 * Author： 王多鱼
 * CreateTime： 2021/7/6 19:57
 **/
// 给两个List a,b，实现两个List两个List的并集，即合并两个List，重复的元素只保留一个。
// 不可以调用现成的集合方法
// 有空闲限制，a的长度是m，b的长度是n，额外空间最多用m+n (不是O(m+n))
// 尝试优化下，最少的时间复杂度是多少，在代码注释里给出最终的时间复杂度
public class ListUnion {
    public static void main(String[] args) {
        // union([ 2, 1, 3], [ 2, 3, 4]) ==  [1, 2, 3, 4]
        System.out.println(union(Arrays.asList(2, 1, 3), Arrays.asList(2, 3, 4)));
    }

    private static List<Integer> union(List<Integer> asList, List<Integer> asList1) {
        List<Integer> list = new ArrayList<>(asList);
        List<Integer> list1 = new ArrayList<>(asList1);
        for (int j = 0; j < list1.size(); j++) {
            list.add(list1.get(j));
        }
        Set<Integer> set = new HashSet(list);
        List<Integer> listRes = new ArrayList<>(set);
        return listRes;
    }
}

